package src.cn.edu.besti.cs1723.LWZ2320;

/**
 * Searching demonstrates various search algorithms on an array 
 * of objects.
 *
 * @author Lewis and Chase
 * @version 4.0 
 */
public class Searching 
{
    /**
     * Searches the specified array of objects using a linear search
     * algorithm.
     *
     * @param data   the array to be searched
     * @param min    the integer representation of the minimum value 
     * @param max    the integer representation of the maximum value
     * @param target the element being searched for
     * @return       true if the desired element is found
     */
    //线性查找
    public static <T>   
		boolean linearSearch(T[] data, int min, int max, T target)
    {
        int index = min;
        boolean found = false;

        while (!found && index <= max) 
        {
            found = data[index].equals(target);
            index++;
        }

        return found;
    }

    /**
     * Searches the specified array of objects using a binary search
     * algorithm.
     *
     * @param data   the array to be searched
     * @param min    the integer representation of the minimum value 
     * @param max    the integer representation of the maximum value
     * @param target the element being searched for 
     * @return       true if the desired element is found
     */
    public static <T extends Comparable<T>>
		boolean binarySearch(T[] data, int min, int max, T target)
    {
        boolean found = false;
        int midpoint = (min + max) / 2;  // determine the midpoint

        if (data[midpoint].compareTo(target) == 0) {
            found = true;
        } else if (data[midpoint].compareTo(target) > 0)
        {
            if (min <= midpoint - 1) {
                found = binarySearch(data, min, midpoint - 1, target);
            }
        }
        else if (midpoint + 1 <= max) {
            found = binarySearch(data, midpoint + 1, max, target);
        }

        return found;
    }
    //顺序查找
    public static int SequenceSearch(int n[], int target, int x){
        int i;
        for (i = 0; i < x; i++){
            if (n[i] == target ) {
                return i;
            }
        }
        return -1;
    }


    //插值查找
    public static int InsertSearch(int a[],int value,int low,int high){
        int result=0;
        int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
        if (a[mid]==value){
            result=a[mid];
        }
        if(a[mid]>value) {
            return InsertSearch(a, value, low, mid-1);
        }
        if(a[mid]<value) {
            return InsertSearch(a, value, mid+1, high);
        }
        return result;
    }
    //斐波那契查找
    public static int FibonacciSearch(int[] a, int n, int key)
    {
        int low = 0;
        int high=n-1;

        int max_size = 20;
        int[] F = new int[max_size];
        F[0] = 1;
        F[1] = 1;
        for (int i = 2; i < max_size; i++){
            F[i] = F[i - 1] + F[i - 2];
        }
        int k=0;
        while(n > F[k]-1)
        {
            k++;
        }
        int[] temp;
        temp = new int [F[k]-1];
        for (int x = 0; x < a.length; x++){
            temp[x] = a[x];
        }
        for(int i=n;i<F[k]-1;++i) {
            temp[i]=a[n-1];
        }
        while(low <= high)
        {
            int mid = low + F[k-1] - 1;
            if(key<temp[mid])
            {
                high = mid - 1;
                k -= 1;
            }
            else if(key > temp[mid])
            {
                low = mid + 1;
                k -= 2;
            }
            else
            {
                if(mid < n) {
                    return mid;
                } else {
                    return n-1;
                }
            }
        }
        return -1;
    }
}

